/**
 * 
 */
package leetCode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;

/**
 * @author zhong
 *
 */
public class WalkingRobotSimulation {
	public int robotSim(int[] commands, int[][] obstacles) {
		int curDir = 0;
		int[] curPos = { 0, 0 };
		HashMap<Integer, ArrayList<Integer>> xObstacles = new HashMap<>();
		HashMap<Integer, ArrayList<Integer>> yObstacles = new HashMap<>();
		for (int[] obs : obstacles) {
			int x = obs[0], y = obs[1];
			if (xObstacles.containsKey(x)) {
				xObstacles.get(x).add(y);
			} else {
				ArrayList<Integer> set = new ArrayList<>();
				set.add(y);
				xObstacles.put(x, set);
			}
			if (yObstacles.containsKey(y)) {
				yObstacles.get(y).add(x);
			} else {
				ArrayList<Integer> set = new ArrayList<>();
				set.add(x);
				yObstacles.put(y, set);
			}
		}
		// 排序
		for (ArrayList<Integer> list : xObstacles.values()) {
			Collections.sort(list);
		}
		for (ArrayList<Integer> list : yObstacles.values()) {
			Collections.sort(list);
		}

		int max = 0;
		for (int command : commands) {
			if (command < 0) {
				curDir = changeDir(curDir, command);
			} else {
				curPos = foreard(curPos, curDir, command, xObstacles, yObstacles);
				int curDis = curPos[0] * curPos[0] + curPos[1] * curPos[1];
				max = Math.max(max, curDis);
			}
		}
		return max;
	}

	/**
	 * 前进，考虑障碍
	 * 
	 * @param curPos
	 * @param curDir
	 * @param command
	 * @param xObstacles
	 * @param yObstacles
	 * @return
	 */
	private int[] foreard(int[] curPos, int curDir, int command, HashMap<Integer, ArrayList<Integer>> xObstacles,
			HashMap<Integer, ArrayList<Integer>> yObstacles) {
		int[] endPos = { curPos[0], curPos[1] };// 预期到达位置
		if (curDir == 0) {
			endPos[1] += command;
		} else if (curDir == 1) {
			endPos[0] += command;
		} else if (curDir == 2) {
			endPos[1] -= command;
		} else {
			endPos[0] -= command;
		}

		if (curDir % 2 == 1) {// 奇数,是左右移动,y不变，x变：检查同一个y上是否有障碍
			int dir = 1;
			if (curPos[0] > endPos[0]) {
				dir = -1;// 反而是减小
			}
			Integer obs = help(yObstacles, endPos[1], curPos[0], endPos[0], dir);// 找到第一个障碍的横坐标
			if (obs == null) {
				return endPos;
			} else {
				endPos[0] = obs - dir;
			}
		} else {// 偶数,是上下移动,检查同一个x上是否有障碍
			int dir = 1;
			if (curPos[1] > endPos[1]) {
				dir = -1;// y反而是减小
			}
			Integer obs = help(xObstacles, endPos[0], curPos[1], endPos[1], dir);// 找到第一个障碍的横坐标
			if (obs == null) {
				return endPos;
			} else {
				endPos[1] = obs - dir;
			}
		}
		return endPos;
	}

	/**
	 * 找到第一个障碍
	 * 
	 * @param Obstacles
	 * @param i
	 * @param j0
	 * @param j1
	 * @param dir
	 * @return
	 */
	private Integer help(HashMap<Integer, ArrayList<Integer>> Obstacles, int i, int j0, int j1, int dir) {// 返回第一个遇到的障碍的位置,1维
		if (!Obstacles.containsKey(i)) {
			return null;
		}
		ArrayList<Integer> list = Obstacles.get(i);

		Integer res = null;
		int id1 = Collections.binarySearch(list, j0);// >=起点的第一个障碍
		int id2 = Collections.binarySearch(list, j1);// >=终点的第一个障碍
		if (id1 < 0) {
			id1 = -id1 - 1;
		}
		if (id2 < 0) {
			id2 = -id2 - 1;
		} else {// 终点本身是障碍
			res = j1;
		}
		if (id1 != id2) {// 这两者之间有障碍

			if (dir == 1) {
				if (id1 == list.size()) {
					return null;
				}
				res = list.get(id1);// 从小往大走。第一个障碍是大于起点的第一个障碍id1
			} else {
				res = list.get(id1 - 1);// 从大向小走的第一个障碍是小于起点的第一个障碍，id1的上一个
			}
		}
		return res;

	}

	private int changeDir(int oriDir, int command) {
		if (command == -1) {// 右转
			return (oriDir + 1) % 4;
		} else {
			return (oriDir + 3) % 4;
		}
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[] commands = { 4, -1, 3 };
		int[][] obstacles = {};
		System.out.println(new WalkingRobotSimulation().robotSim(commands, obstacles));
	}

}
